package main

import (
	"fmt"
)

/**
执行用时：4 ms, 在所有 Go 提交中击败了58.52%的用户
内存消耗：2.5 MB, 在所有 Go 提交中击败了5.15%的用户
 */
func divide(x int, y int) int {

	sign := (x > 0) == (y > 0)
	if x > 0 { x = -x }
	if y > 0 { y = -y }

	ys := [][]int{}
	for a, b := y, -1; a >= x; a, b = a + a, b + b {
		ys = append(ys, []int{a, b})
		if a < HALF_INT_MIN { break }
	}

	res := 0
	for i := len(ys) - 1; i >= 0; i-- {
		if x <= ys[i][0] {
			x -= ys[i][0]
			res += ys[i][1]
		}
	}

	if sign {  // 说明返回正数
		if res == INT_MIN { return INT_MAX }
		res = -res
	}
	return res
}

const INT_MAX = (1 << 31) - 1
const INT_MIN = -(1 << 31)
const HALF_INT_MIN = -(1 << 30)

func main() {

	fmt.Println(divide(10, 3))
	fmt.Println(divide(INT_MIN, -1))
}
